
#include <string.h>
#include <string>
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>
#include <stdbool.h>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
// #include <windows.h>
using namespace std;

#define MAX 9999
#define MVNum 20             // 最大地点数
typedef pair<int, int> Pair; // 数据类型
typedef struct Location      // 顶点信息
{
    char name[200];
    int x, y;
    char intro[10000];
} Location;
typedef struct Campus_Route // 地图信息
{
    int vexnum;
    Location vexs[MVNum];
    int arcs[MVNum][MVNum];
    int arcnum;
} Map;
void Dijkstra(const Map *map, int obj)
{
    vector<int> objTo(map->vexnum, MAX); // obj到其他各顶点的距离 初始为MAX 更新后为obj到其他各顶点的最短简单路径的距离
    vector<int> prev(map->vexnum, -1);   // 从obj到other的最短路径中 other前驱顶点的标号other前无顶点 存-1
    vector<Pair> sortedPaths;            // 此时objTo数组中的数据为obj到其他各顶点的最短简单路径的距离 将pair存入vector中 以便使用sort函数
    priority_queue<Pair, vector<Pair>, greater<Pair>> pq;
    objTo[obj] = 0;             // 点到自身距离为0
    pq.push({objTo[obj], obj}); // obj点入队

    while (!pq.empty())
    {
        int New = pq.top().second;
        pq.pop();

        for (int other = 0; other < map->vexnum; ++other)
        {
            int NewtoOther = map->arcs[New][other];
            if (NewtoOther != 0                            // 当other遍历至new时 距离为0 不进行更新
                && objTo[New] != MAX                       // 当obj到New无边时 不进行更新
                && objTo[New] + NewtoOther < objTo[other]) // 当由于New的加入 使得obj到other的距离缩短 ==> 更新
            {
                objTo[other] = objTo[New] + NewtoOther;
                prev[other] = New; // prev[other]: 从obj到other的最短路径中 other的前一个顶点的标号
                pq.push({objTo[other], other});
            }
        }
    }
    for (int i = 0; i < map->vexnum; ++i)
    {
        if (i != obj            // 当i遍历至obj时 objTo[obj] 无意义 不存
            && objTo[i] != MAX) // 无路径不存
            sortedPaths.push_back({objTo[i], i});
    }
    // 排序后 sortedPaths中的数据为{obj到other的距离,other} 按距离递增存储
    sort(sortedPaths.begin(), sortedPaths.end()); // 默认递增排序Pair的第一个参数
}
